package com.mianshi;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 01矩阵
 */
public class bole2 {
    public int[][] UpdateMatrix (int[][] matrix) {
        // write code here
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] ans = new int[m][n];
        boolean[][] used = new boolean[m][n];
        int[][] pos = {{-1,0},{1,0},{0,-1},{0,1}};
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    queue.offer(new int[]{i,j});
                    used[i][j] = true;
                }
            }
        }
        while(!queue.isEmpty()){
            int[] item = queue.poll();
            int i = item[0], j = item[1];
            for(int d = 0; d < 4; d++){
                int next_i = i + pos[d][0];
                int next_j = j + pos[d][1];
                if(next_i >= 0 && next_i < m && next_j >= 0 && next_j < n && !used[next_i][next_j]){
                    ans[next_i][next_j] = ans[i][j] + 1;
                    queue.offer(new int[]{next_i,next_j});
                    used[next_i][next_j] = true;
                }
            }
        }
        return ans;
    }

    public int dfs(int i, int j, int m, int n, int[][] matrix){
        int ans = 1;
        if(i < 0 || i >= m || j < 0 || j >= n){
            return ans;
        }
        if(matrix[i][j] == 0){
            return ans;
        } else {
            ans++;
        }
        return Math.min(Math.min(dfs(i-1,j,m,n,matrix),dfs(i+1,j,m,n,matrix)),
                Math.min(dfs(j+1,i,m,n,matrix),dfs(i,j-1,m,n,matrix)));
    }
}
